package algorithm;

import java.util.Stack;

// "9,3,4,#,#,1,#,#,2,#,6,#,#"
public class Leetcode331 {

    public static boolean isValidSerialization(String preorder) {
        Stack<Character> stack = new Stack<>();
        boolean hasNumber = false;
        for (int i = 0; i < preorder.length(); i++) {
            if (Character.isDigit(preorder.charAt(i))) {
                hasNumber = true;
            } else if (preorder.charAt(i) == ',') {
                if (hasNumber) {
                    stack.push('1');
                    hasNumber = false;
                }
            } else {
                if (stack.peek() == '#') {
                    Character temp = stack.pop();
                    if (stack.peek() == '1') {
                        stack.pop();
                    } else {
                        stack.push(temp);
                    }
                }
                stack.push('#');
            }
        }
        while (!stack.isEmpty()) {
            boolean flag = stack.pop() == '#';
            if (!stack.isEmpty()) {
                flag = stack.pop() == '#';
            } else {
                flag = false;
            }

            if (flag || stack.pop() != '1') {
                break;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#"));
    }
}
